{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Integer Replacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #memoization #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #记忆化搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: integerReplacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #整数替换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数&nbsp;<code>n</code> ，你可以做如下操作：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>如果&nbsp;<code>n</code><em>&nbsp;</em>是偶数，则用&nbsp;<code>n / 2</code>替换&nbsp;<code>n</code><em> </em>。</li>\n",
    "\t<li>如果&nbsp;<code>n</code><em>&nbsp;</em>是奇数，则可以用&nbsp;<code>n + 1</code>或<code>n - 1</code>替换&nbsp;<code>n</code> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回 <code>n</code><em>&nbsp;</em>变为 <code>1</code> 所需的 <em>最小替换次数</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>8 -&gt; 4 -&gt; 2 -&gt; 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1\n",
    "或 7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [integer-replacement](https://leetcode.cn/problems/integer-replacement/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [integer-replacement](https://leetcode.cn/problems/integer-replacement/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['8', '7', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        \n",
    "        def dfs(i):\n",
    "            if i==1:\n",
    "                return 0\n",
    "            if i%2==1:\n",
    "                return min(dfs(i+1),dfs(i-1))+1\n",
    "            if i%2==0:\n",
    "                return dfs(i//2)+1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        res = 0\n",
    "        cur_level = [n]\n",
    "        seen = set()\n",
    "        seen.add(n)\n",
    "        while True:\n",
    "            next_level = []\n",
    "            for num in cur_level:\n",
    "                if num == 1:\n",
    "                    return res\n",
    "                if num % 2:\n",
    "                    if num + 1 not in seen:\n",
    "                        next_level.append(num + 1)\n",
    "                    if num - 1 not in seen:\n",
    "                        next_level.append(num - 1)\n",
    "                else:\n",
    "                    if num // 2 not in seen:\n",
    "                        next_level.append(num // 2)\n",
    "            res += 1\n",
    "            cur_level = next_level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        def digui(num,path,stack):\n",
    "            if num==1:\n",
    "                stack.append(path)\n",
    "                return\n",
    "            if num%2==0:\n",
    "                digui(num//2,path+1,stack)\n",
    "            else:\n",
    "                digui(num+1,path+1,stack)\n",
    "                digui(num-1,path+1,stack)\n",
    "        stack=[]\n",
    "        digui(n,0,stack)\n",
    "        return min(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n > 1:\n",
    "            if n % 2 == 0:\n",
    "                res += 1\n",
    "                n //= 2\n",
    "            elif n % 4 == 1:\n",
    "                res += 2\n",
    "                n //= 2\n",
    "            else:\n",
    "                res += 2\n",
    "                if n == 3:\n",
    "                    n = 1\n",
    "                else:\n",
    "                    n = n // 2 +1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        # if n == 1:\n",
    "        #     return 0\n",
    "        # if n % 2 == 0:\n",
    "        #     return 1 + self.integerReplacement(n // 2)\n",
    "        # return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))\n",
    "        # ======================================================================================\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        c = 0\n",
    "        while n != 1:\n",
    "            if n % 2 == 0:\n",
    "                n = n // 2\n",
    "                c = c + 1\n",
    "            else:\n",
    "                n = n - 1 if (((n - 1) // 2) % 2 == 0 or n == 3) else n + 1\n",
    "                c = c + 1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        \n",
    "        '''动态规划，空间复杂度超了'''\n",
    "        # DP = [n]*(n+1)\n",
    "        # DP[0] = 0\n",
    "        # DP[1] = 0\n",
    "        # DP[2] = 1\n",
    "        # for i in range(3,n+1):\n",
    "        #     if i%2 == 0:\n",
    "        #         DP[i] = min(DP[i],DP[int(i/2)]+1)\n",
    "                \n",
    "        #     else:\n",
    "        #         DP[i] = min(DP[i],DP[int((i-1)/2)]+2,DP[int((i+1)/2)]+2)\n",
    "        # return DP[n]\n",
    "\n",
    "\n",
    "        '''贪心算法'''\n",
    "        num = 0\n",
    "        while n > 1:\n",
    "            if n == 3 or n == 4:\n",
    "                num += 2\n",
    "                break\n",
    "            else:\n",
    "\n",
    "                '''用4来区分是+1合适，还是-1合适'''\n",
    "                if (n+1)%4 == 0:\n",
    "                    n = int((n+1)/4)\n",
    "                    num += 3\n",
    "                elif (n-1)%4 == 0:\n",
    "                    n = int((n-1)/4)\n",
    "                    num += 3\n",
    "                else:\n",
    "                    n = int(n/2)\n",
    "                    num +=1\n",
    "\n",
    "        return num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\"\"\" \n",
    "2023-10-10\n",
    "    当遇到偶数时, 直接处于 2;\n",
    "    当遇到奇数时, 将其变为偶数, 有两种选择, 分别比较两种选择的大小;\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        mem = {}\n",
    "        ## 计算将 n 变为 1 的次数\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "\n",
    "            if n in mem:\n",
    "                return mem[n]\n",
    "            ## n 为偶数\n",
    "            if n % 2 == 0:\n",
    "                mem[n] = 1 + dfs(n // 2)\n",
    "                return mem[n]\n",
    "            ## n 为奇数\n",
    "            mem[n] =  2 + min(   ## NOTE 这里是加 2, 不是 1, 因为执行了两次操作: 1. 加 1 或者减 1; 2) 除以 2\n",
    "                dfs(n //2 + 1), dfs(n//2)\n",
    "            )\n",
    "            return mem[n]\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        q=collections.deque()\n",
    "        q.append(n)\n",
    "        ans=0\n",
    "        while q:\n",
    "            layer_count=len(q)\n",
    "            for i in range(layer_count):\n",
    "                tmp_n=q.popleft()\n",
    "                if tmp_n==1:\n",
    "                    return ans\n",
    "                elif tmp_n%2==0:\n",
    "                    q.append(tmp_n/2)\n",
    "                else:\n",
    "                    q.append(tmp_n+1)\n",
    "                    q.append(tmp_n-1)\n",
    "            ans+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n != 1:\n",
    "            if n % 2 == 0:\n",
    "                ans += 1\n",
    "                n //= 2\n",
    "            elif n % 4 == 1:\n",
    "                ans += 2\n",
    "                n //= 2\n",
    "            else:\n",
    "                if n == 3:\n",
    "                    ans += 2\n",
    "                    n = 1\n",
    "                else:\n",
    "                    ans += 2\n",
    "                    n = n // 2 + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n != 1:\n",
    "            if n % 2 == 0:\n",
    "                ans += 1\n",
    "                n //= 2\n",
    "            elif n % 4 == 1:\n",
    "                ans += 2\n",
    "                n //= 2\n",
    "            else:\n",
    "                if n == 3:\n",
    "                    ans += 2\n",
    "                    n = 1\n",
    "                else:\n",
    "                    ans += 2\n",
    "                    n = n // 2 + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        def change(n: int):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                return 1 + change(n // 2)\n",
    "            else:\n",
    "                return min(1 + change(n + 1), 1 + change(n - 1))\n",
    "        return change(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if (n == 1):\n",
    "            return 0\n",
    "        elif (n%2 == 0):\n",
    "            return self.integerReplacement(n/2) + 1\n",
    "        else:\n",
    "            a = self.integerReplacement(n+1)\n",
    "            b = self.integerReplacement(n-1)\n",
    "            if (a>b):\n",
    "                return b + 1\n",
    "            else:\n",
    "                return a + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        def dfs(cur):\n",
    "            if cur == 1:return 0\n",
    "            if cur % 2 == 0:\n",
    "                return dfs(cur // 2) + 1\n",
    "            return min(dfs(cur + 1), dfs(cur - 1)) + 1\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        def zongshu(n):\n",
    "            if (n == 1):\n",
    "                return 0;\n",
    "            if (n % 2 == 0):\n",
    "                return 1 + zongshu(n/2);\n",
    "            else:\n",
    "                return 2 + min(zongshu((n+1)/2),zongshu((n-1)/2))\n",
    "        return zongshu(n)\n",
    "        # m = 0;\n",
    "\n",
    "        # while n >= 4:\n",
    "        #     print(n,m)\n",
    "        #     if (n % 2 == 0):\n",
    "        #         m = m + 1;\n",
    "        #         n = n / 2;\n",
    "        #     else:\n",
    "        #         m += 1;\n",
    "        #         a = n + 1;\n",
    "        #         b = n - 1;\n",
    "        #         if (a % 4 == 0):\n",
    "        #             n = a;\n",
    "        #         else:\n",
    "        #             n = b;\n",
    "        # if (n == 1):\n",
    "        #     return  m+0;\n",
    "        # elif (n == 2):\n",
    "        #     return m+1;\n",
    "        # else:\n",
    "        #     return m+2;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        if n==1:\n",
    "            return 0\n",
    "        if n==2:\n",
    "            return 1\n",
    "        \n",
    "        if n%2 ==0 :\n",
    "            return self.integerReplacement(n/2)+1\n",
    "        else:\n",
    "            return min(self.integerReplacement(n-1),self.integerReplacement(n+1))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "\n",
    "        '递归'\n",
    "        if n == 1:return 0\n",
    "        if n % 2 == 0:return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n//2), self.integerReplacement(n // 2 + 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n // 2),self.integerReplacement(n // 2 + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        dct = {}\n",
    "        dct[1] = 0\n",
    "        def solve(n):\n",
    "            if n in dct:\n",
    "                return dct[n]\n",
    "            if n % 2 == 0:\n",
    "                res = solve(n/2) + 1\n",
    "            else:\n",
    "                res = min(solve(n+1), solve(n-1)) + 1\n",
    "            dct[n] = res\n",
    "            return res\n",
    "        return solve(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        if n==2:\n",
    "            return 1\n",
    "        if n%2==0:\n",
    "            n1=self.integerReplacement(n//2)+1\n",
    "        else:\n",
    "            n1=self.integerReplacement(n-1)\n",
    "            n2=self.integerReplacement(n+1)\n",
    "            n1=min(n1,n2)+1\n",
    "        return n1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        def dfs(n:int):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                return dfs(n//2)+1\n",
    "            return min(dfs(n+1),dfs(n-1))+1\n",
    "        return dfs(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n==1: return 0\n",
    "        if n%2==0:\n",
    "            return 1 + self.integerReplacement(n//2)\n",
    "        else:\n",
    "            return 1+min(self.integerReplacement(n+1), self.integerReplacement(n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(l):\n",
    "            if l in memo:\n",
    "                return memo[l]\n",
    "            if l == 1:\n",
    "                return 0\n",
    "            if l % 2 == 0:\n",
    "                memo[l] = 1 + dfs(l // 2)\n",
    "            else:\n",
    "                memo[l] = 1 + min(dfs(l - 1), dfs(l + 1))\n",
    "            return memo[l]\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n != 1:\n",
    "            if (n & 1) == 0:\n",
    "                n >>= 1\n",
    "            else:\n",
    "                n += -1 if (n & 2) == 0 or n == 3 else 1  \n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        res=0\n",
    "        while n!=1:\n",
    "            if n%2!=0:\n",
    "                if n==3:\n",
    "                    n=n-1\n",
    "                elif ((n-1)/2)%2==0:\n",
    "                    n=n-1\n",
    "                else:\n",
    "                    n=n+1\n",
    "                res+=1\n",
    "                print(n)\n",
    "            n=n/2\n",
    "            res+=1\n",
    "            print(n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == 1: return 0\n",
    "\n",
    "            if x % 2 == 0: return dfs(x>>1) + 1\n",
    "            \n",
    "            return min(dfs(x+1), dfs(x-1)) + 1\n",
    "    \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(num):\n",
    "            if num == 1: return 0\n",
    "            if num % 2 == 0: return dfs(num // 2) + 1\n",
    "            return min(dfs(num + 1), dfs(num - 1)) + 1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n != 1:\n",
    "            count += 1\n",
    "            if n & 1 == 0:\n",
    "                n = n >> 1\n",
    "            elif n & 3 == 1 or n == 3:\n",
    "                n -= 1\n",
    "            else:\n",
    "                n += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        elif n % 2 ==0:\n",
    "            return 1+self.integerReplacement(n//2)\n",
    "        else:\n",
    "            return 2 + min(self.integerReplacement((n-1)//2),self.integerReplacement((n+1)//2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        return self.single_step(n=n, step=0)\n",
    "\n",
    "    def single_step(self, n: int, step: int) -> int:\n",
    "        if n == 1:\n",
    "            return step\n",
    "        if self.is_even_number(n):\n",
    "            return self.single_step(n=n / 2, step=step+1)\n",
    "        else:\n",
    "            return min(self.single_step(n=(n+1)/2, step=step+2), self.single_step(n=(n-1)/2, step=step+2))\n",
    "\n",
    "    @staticmethod\n",
    "    def is_even_number(n: int) -> bool:\n",
    "        return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        def helper(ans, n):\n",
    "            if n == 1:\n",
    "                return ans\n",
    "            if n % 2 == 0:\n",
    "                return helper(ans + 1, n // 2)\n",
    "            return min(helper(ans + 1, n - 1), helper(ans + 1, n + 1))\n",
    "        return helper(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                return dfs(n//2)+1\n",
    "            return min(dfs(n+1), dfs(n-1))+1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n != 1:\n",
    "            # 偶数(0bXX0)直接右移\n",
    "            if (n & 1) == 0:\n",
    "                n >>= 1\n",
    "            else:\n",
    "                #大于1的奇数格式为XX01或者XX11，对于前一种格式直接-1，对于后一种格式直接+1\n",
    "                #单且仅当只有两位时候0b01(十进制的1)和0b11（十进制的3）时候，对于3，最少的步数应该是-1，因为3 - 1 = 2 / 2 = 1（三步）                #如果+1的话是3 + 1= 4 /2 =  2 / 2 = 1（四步），造成3这个数字比较特殊的原因是因为3的二进制只有2bit(0b11)\n",
    "                n += -1 if (n & 2) == 0 or n == 3 else 1  \n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        q = deque()\n",
    "        q.append(n)\n",
    "        level = 0\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        vis = set()\n",
    "        vis.add(n)\n",
    "        while q:\n",
    "            s = len(q)\n",
    "            for i in range(s):\n",
    "                tt = q.popleft()\n",
    "                if tt == 1:\n",
    "                    return level\n",
    "                if tt % 2 == 0:\n",
    "                    if tt // 2 not in vis:\n",
    "                        q.append(tt // 2)\n",
    "                        vis.add(tt//2)\n",
    "                else:\n",
    "                    if tt - 1 not in vis:\n",
    "                        q.append(tt - 1)\n",
    "                        vis.add(tt -1)\n",
    "                    if tt + 1 not in vis:\n",
    "                        q.append(tt + 1)\n",
    "                        vis.add(tt +1)\n",
    "            level += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        def mintimes(n: int):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                return mintimes(n / 2) + 1\n",
    "            else:\n",
    "                left = mintimes(n - 1) + 1\n",
    "                right = mintimes(n + 1) + 1\n",
    "                return min(left, right)\n",
    "\n",
    "        return mintimes(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 1:\n",
    "                return 0\n",
    "            if i % 2 == 0:\n",
    "                return dfs(i // 2) + 1\n",
    "            return min(dfs(i // 2), dfs(i //2 + 1)) + 2\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def recur(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n%2:\n",
    "                return min(recur(n+1),recur(n-1))+1\n",
    "            else:\n",
    "                return 1+ recur(n//2)\n",
    "        return recur(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x & 1 == 0:\n",
    "                return dfs(x//2)+1\n",
    "            else:\n",
    "                return min(dfs(x+1), dfs(x-1))+1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        count = n+1\n",
    "\n",
    "        def search(m,k):\n",
    "            nonlocal count \n",
    "            if m==1:\n",
    "                count = min(count,k)\n",
    "                return \n",
    "            if m % 2 == 0:\n",
    "                m = m//2\n",
    "                k += 1\n",
    "                search(m,k)\n",
    "            \n",
    "\n",
    "            else:\n",
    "                k+=1\n",
    "                search(m+1,k)\n",
    "                \n",
    "                search(m-1,k)\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        search(n,0)\n",
    "        return count\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def mintimes(n: int):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n in memo.keys():\n",
    "                return memo[n]\n",
    "            if n % 2 == 0:\n",
    "                res = mintimes(int(n / 2)) + 1\n",
    "                memo[n] = memo.get(n, 0) + res\n",
    "                return res\n",
    "            else:\n",
    "                left = mintimes(n - 1) + 1\n",
    "                right = mintimes(n + 1) + 1\n",
    "                res = min(left, right)\n",
    "                memo[n] = memo.get(n, 0) + res\n",
    "                return res\n",
    "\n",
    "        return mintimes(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @lru_cache\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                return dfs(n / 2) + 1\n",
    "            return min(dfs(n + 1) + 1, dfs(n - 1) + 1)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n // 2 + 1), self.integerReplacement(n // 2))\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x & 1 == 0:\n",
    "                return dfs(x//2)+1\n",
    "            else:\n",
    "                return min(dfs(x+1), dfs(x-1))+1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache \n",
    "def dp(t):\n",
    "    if t == 1: return 0\n",
    "\n",
    "    if t % 2 == 0: return dp(t // 2) + 1\n",
    "    return min(dp(t + 1), dp(t - 1)) + 1\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        # 动态规划\n",
    "        @cache\n",
    "        def func(n):\n",
    "            if n==1:\n",
    "                return 0\n",
    "            if n%2==0:\n",
    "                return func(n//2)+1\n",
    "            return min(func(n-1),func(n+1))+1\n",
    "\n",
    "        return func(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n > 1:\n",
    "            count += 1\n",
    "            if n % 2 == 0:\n",
    "                n = n // 2\n",
    "            elif n % 4 == 1 or n == 3:\n",
    "                n = n - 1\n",
    "            else :\n",
    "                n = n +1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        global cou\n",
    "        cou = math.inf\n",
    "        def count_my(n,count):\n",
    "            global cou\n",
    "            if count >= cou:\n",
    "                return\n",
    "            if n == 1:\n",
    "                cou = count\n",
    "                return\n",
    "            if n//2 ==n/2:\n",
    "                count_my(n//2,count+1)\n",
    "            else:\n",
    "                count_my(n+1,count+1)\n",
    "                count_my(n-1,count+1)\n",
    "        count_my(n,0)\n",
    "        return cou"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return 0 \n",
    "            if n%2 ==0:\n",
    "                return dfs(n//2) + 1 \n",
    "            else:\n",
    "                return min(dfs((n+1)//2), dfs((n-1)//2)) + 2 \n",
    "        return dfs(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==1:\n",
    "                return 0\n",
    "            else:\n",
    "                if i%2==0:\n",
    "                    return dfs(i//2) + 1\n",
    "                else:\n",
    "                    return min(dfs(i+1), dfs(i-1)) + 1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        return 0 if n == 1 else (\n",
    "            self.integerReplacement(n // 2) + 1 if not n % 2  else min(self.integerReplacement(n - 1),\n",
    "                                                                           self.integerReplacement(n + 1))+1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        def replace(n: int):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                return replace(n // 2) + 1\n",
    "            else:\n",
    "                return min(replace(n + 1), replace(n - 1)) + 1\n",
    "\n",
    "        return replace(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        \n",
    "        ans=float(\"inf\")\n",
    "        def dfs(n,t):\n",
    "            nonlocal ans\n",
    "            if n==1:\n",
    "                ans=min(ans,t)\n",
    "                return\n",
    "            if t>ans:\n",
    "                return \n",
    "            if n%2==0:\n",
    "                \n",
    "                dfs(n//2,t+1)\n",
    "            else:\n",
    "                dfs(n-1,t+1)\n",
    "                dfs(n+1,t+1)\n",
    "            return \n",
    "        dfs(n,0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def mintimes(n: int):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n % 2 == 0:\n",
    "                res = mintimes(int(n / 2)) + 1\n",
    "                memo[n] = memo.get(n, 0) + res\n",
    "                return res\n",
    "            else:\n",
    "                left = mintimes(n - 1) + 1\n",
    "                right = mintimes(n + 1) + 1\n",
    "                res = min(left, right)\n",
    "                memo[n] = memo.get(n, 0) + res\n",
    "                return res\n",
    "\n",
    "        return mintimes(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        res_dict = {\n",
    "            1: 0,\n",
    "            2: 1,\n",
    "        }\n",
    "\n",
    "        def dfs(n):\n",
    "            if n in res_dict:\n",
    "                return res_dict[n]\n",
    "            if n % 2 == 0:\n",
    "                res = dfs(n / 2) + 1\n",
    "                res_dict[n] = res\n",
    "                return res\n",
    "            else:\n",
    "                res =  min(dfs(n + 1), dfs(n - 1)) + 1\n",
    "                res_dict[n] = res\n",
    "                return res\n",
    "        return dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==1:\n",
    "                return 0\n",
    "            if i%2==1:\n",
    "                ans=min(dfs(i+1),dfs(i-1))+1\n",
    "            else:\n",
    "                ans=dfs(i//2)+1\n",
    "            return ans\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(num):\n",
    "            if num == 1:\n",
    "                return 0\n",
    "            if num % 2 == 0:\n",
    "                return 1 + dfs(num / 2)\n",
    "            return 1 + min(dfs(num - 1), dfs(num + 1))\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "  @cache\n",
    "  def integerReplacement(self, n: int) -> int:\n",
    "    if n == 1:\n",
    "      return 0\n",
    "    if n % 2 == 0:\n",
    "      return 1 + self.integerReplacement(n // 2)\n",
    "    else:\n",
    "      return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 1:\n",
    "                return 0\n",
    "            if i % 2 == 0:\n",
    "                return dfs(i//2) + 1\n",
    "            else:\n",
    "                return min(dfs(i+1),dfs(i-1)) + 1\n",
    "        return dfs(n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "           return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return min(self.integerReplacement(n//2 ) + 2,self.integerReplacement((n+1)//2 ) + 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n > 1:\n",
    "            if n % 2 == 0:\n",
    "                count = self.integerReplacement(n / 2) + 1\n",
    "            else:\n",
    "                count = min(self.integerReplacement(n - 1), self.integerReplacement(n + 1)) + 1\n",
    "        elif n == 1:\n",
    "            count = 0\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n & 1:\n",
    "            return min(self.integerReplacement(n + 1), self.integerReplacement(n - 1)) + 1\n",
    "        return self.integerReplacement(n // 2) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,cnt):\n",
    "            if i == 1:\n",
    "                return cnt\n",
    "            if i & 1 == 0:\n",
    "                return dfs(i>>1,cnt+1)\n",
    "            return min(dfs(i+1,cnt+1),dfs(i-1,cnt+1))\n",
    "        return dfs(n,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n==1 :\n",
    "            return 0\n",
    "        \n",
    "        if n%2==0:\n",
    "            return self.integerReplacement(n//2)+1\n",
    "        else:\n",
    "            return min(self.integerReplacement(n-1)+1,self.integerReplacement(n+1)+1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(num: int) -> int:\n",
    "            if num == 1:\n",
    "                return 0\n",
    "            if num == 0:\n",
    "                return 1\n",
    "            ret = inf\n",
    "            if num & 1:\n",
    "                return min(dfs(num + 1), dfs(num - 1)) + 1\n",
    "            else:\n",
    "                return dfs(num // 2) + 1\n",
    "\n",
    "        return dfs(n)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        dp = {}\n",
    "        @lru_cache() #最近最先\n",
    "        def dfs(i):\n",
    "            if i == 1:return 0\n",
    "            if i % 2==0:\n",
    "                return dfs(i/2) + 1\n",
    "            return min(dfs(i+1) , dfs(i-1)) + 1 \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        res = set()\n",
    "        @cache\n",
    "        def dfs(n, time):\n",
    "            if n == 1:\n",
    "                res.add(time)\n",
    "                return\n",
    "            if not(n % 2):\n",
    "                dfs(n//2, time+1)\n",
    "            else:\n",
    "                dfs(n+1, time+1)\n",
    "                dfs(n-1, time+1)\n",
    "        dfs(n, 0)\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n & 1:\n",
    "            return min(self.integerReplacement(n + 1), self.integerReplacement(n - 1)) + 1\n",
    "        return self.integerReplacement(n // 2) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        ans = 1e9\n",
    "        @cache\n",
    "        def opt(n, step):\n",
    "            if n == 1: \n",
    "                nonlocal ans\n",
    "                ans = min(ans, step)\n",
    "                return \n",
    "            if n%2 == 0: \n",
    "                opt(n//2, step+1)\n",
    "            else:\n",
    "                opt(n+1, step+1)\n",
    "                opt(n-1, step+1)\n",
    "        opt(n, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n & 1:\n",
    "            return min(self.integerReplacement(n + 1), self.integerReplacement(n - 1)) + 1\n",
    "        return self.integerReplacement(n // 2) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        res = []\n",
    "        @lru_cache(10000)\n",
    "        def dfs(n, time):\n",
    "            if n == 1:\n",
    "                res.append(time)\n",
    "                return\n",
    "            if not(n % 2):\n",
    "                dfs(n//2, time+1)\n",
    "            else:\n",
    "                dfs(n+1, time+1)\n",
    "                dfs(n-1, time+1)\n",
    "        dfs(n, 0)\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        bfs = [(n, 0)]\n",
    "        while bfs[0][0] != 1 :\n",
    "            if bfs[0][0] & 1 :\n",
    "                if bfs[0][0] - 1 >= 0 :\n",
    "                    bfs.append((bfs[0][0]-1, bfs[0][1]+1))\n",
    "                bfs.append((bfs[0][0]+1, bfs[0][1]+1))\n",
    "            else :\n",
    "                bfs.append((bfs[0][0] // 2, bfs[0][1]+1))\n",
    "            bfs.pop(0)\n",
    "        return bfs[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        res = []\n",
    "        @lru_cache(1000000)\n",
    "        def dfs(n, time):\n",
    "            if n == 1:\n",
    "                res.append(time)\n",
    "                return\n",
    "            if not(n % 2):\n",
    "                dfs(n//2, time+1)\n",
    "            else:\n",
    "                dfs(n+1, time+1)\n",
    "                dfs(n-1, time+1)\n",
    "        dfs(n, 0)\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return 1 + self.integerReplacement(n // 2)\n",
    "        return min(self.integerReplacement(n + 1),self.integerReplacement(n - 1)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def sub(self,x):\n",
    "        if x==1:\n",
    "            return 0\n",
    "        if x%2==0:\n",
    "            return self.sub(x//2)+1\n",
    "        else:\n",
    "            return min(self.sub(x+1),self.sub(x-1))+1\n",
    "    def integerReplacement(self, n: int) -> int:\n",
    "        return self.sub(n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
